#include "Johnson.hpp"


/**
 * @brief 单源最短路径算法初始化
 * 
 * @param G 输入的带权有向图
 * @param s 输入的源的索引
 */
void Johnson::Initialize_Single_Source(Weight_Directed_Graph *G, int s){
    for (size_t i = 0; i < (*G).n_V; i++)
    {
        (*G).V[i]->d = 2000000000;
        (*G).V[i]->pi = nullptr;
    }
    (*G).V[s]->d = 0;
}


/**
 * @brief Bellman-Ford算法中的松弛操作
 * 
 * @param u 第一个节点
 * @param v 第二个节点
 * @param w 邻接矩阵指针
 */
void Johnson::Relax(vertex* u, vertex* v, vector<vector<int>>* w){
    if(v->d > u->d + (*w)[u->index][v->index]){
        v->d = u->d + (*w)[u->index][v->index];
        v->pi = u;
    }
}


/**
 * @brief 运行Bellman-Ford算法
 * 
 * @param G 输入的图指针（用邻接表表示）
 * @param s 源节点索引
 * @param w 邻接矩阵
 * @return true 
 * @return false 
 */
bool Johnson::run_Bellman_Ford(Weight_Directed_Graph *G, int s, vector<vector<int>>* w){
    Initialize_Single_Source(G, s);
    for (size_t i = 0; i < G->n_V - 1; i++)
    {
        //遍历每一个边
        for (size_t u_i = 0; u_i < G->n_V; u_i++)
        {
            vertex* p = G->V[u_i];
            while (p != nullptr)
            {
                if (p->next != nullptr)
                {
                    Relax(G->V[u_i], G->V[p->next->index], w);
                }
                p = p->next;
            }
        }
    }
    //遍历每一个边
    for (size_t u_i = 0; u_i < G->n_V; u_i++)
    {
        vertex* p = G->V[u_i];
        while (p != nullptr)
        {
            if (p->next != nullptr)
            {
                if(G->V[p->next->index]->d > G->V[u_i]->d + (*w)[u_i][p->next->index]) return false;
            }
            p = p->next;
        }
    }
    return true;
}


/**
 * @brief 输出Bellman-Ford的运行结果
 * 
 * @param G 已经运行完run_Bellman_Ford后存储了运行结果的图
 * @param s 源节点下标
 */
void Johnson::output_BellmanFord_result(Weight_Directed_Graph *G, int s){
    for (size_t i = 0; i < G->n_V; i++)
    {
        if (i != s && G->V[i]->d < 2000000000)
        {
            cout << s << ',' << i << ',' << G->V[i]->d << ';';
            cout << s << ',';
            vector<vertex*> stack;
            for (vertex* pi = G->V[i]; pi != G->V[s];)
            {
                stack.push_back(pi);
                if (pi->pi != nullptr)
                {
                    pi = pi->pi;
                }
                
            }
            while (stack.size())
            {
                cout << stack.back()->index;
                if (stack.back()->index != i)
                {
                    cout << ',';
                }
                
                stack.pop_back();
            }
            cout << endl;
        }
    }
}



/**
 * @brief 运行Dijkstra算法
 * 
 * @param G 输入的图指针
 * @param s 源节点索引
 * @param w 邻接矩阵
 */
void Johnson::run_Dijkstra(Weight_Directed_Graph *G, int s, vector<vector<int>>* w){
    Initialize_Single_Source(G, s);
    set<int> S;
    vector<vertex*> Q;
    for (size_t i = 0; i < G->n_V; i++)
    {
        Q.push_back(G->V[i]);
    }
    while (!Q.empty())
    {
        //extract min
        auto u = Q[0];
        auto it_min = Q.begin();
        auto it = Q.begin();
        for (auto vertex_v: Q)
        {
            if (vertex_v->d < u->d)
            {
                u = vertex_v;
                it_min = it;
            }
            it ++;
        }
        Q.erase(it_min);
        
        //for each vertex in Adj[u]
        vertex* p = u;
        while (p != nullptr)
        {
            if (p->next != nullptr)
            {
                Relax(u, G->V[p->next->index], w);
            }
            p = p->next;
        }
    }
}


/**
 * @brief 运行Johnson算法
 * 
 * @param G 输入的图指针
 * @param w 输入的邻接矩阵指针
 * @return vector<vector<vector<int>>> 存放节点之间最短路径长度的n*n矩阵,和存放前驱结点索引的n*n矩阵
 */
vector<vector<vector<int>>> Johnson::run_Johnson(Weight_Directed_Graph *G, vector<vector<int>>* w){
    //返回值
    auto D = *w;
    auto PI = *w;

    //compute G' by add a new vertex to G
    vector<vertex*> V_ = G->V;
    auto s = new vertex;
    s->index = G->n_V;
    auto p = s;
    vector<int> w_s;
    for (size_t i = 0; i < G->n_V; i++)
    {
        w_s.push_back(0);
        p->next = new vertex;
        p->next->index = i;
        p->next->next = nullptr;
        p = p->next;
    }
    V_.push_back(s);
    w->push_back(w_s);
    auto G_ = Weight_Directed_Graph(V_);
    G->need_free_memory = false;
    //end compute

    vector<int> h = vector<int>(G_.n_V);
    auto w_ = *w;
    if (run_Bellman_Ford(&G_, s->index, w) == false)
    {
        cout << "The input graph contains a negative-weight circle";
        return {D, PI};
    }
    else{
        for (auto v: G_.V)
        {
            h[v->index] = v->d;
        }
        //遍历每一条边
        for (size_t u_i = 0; u_i < G_.n_V; u_i++)
        {
            vertex* p = G_.V[u_i];
            while (p != nullptr)
            {
                if (p->next != nullptr)
                {
                    w_[u_i][p->next->index] = (*w)[u_i][p->next->index] + h[u_i] - h[p->next->index];
                }
                p = p->next;
            }
        }

        for (auto vertex_u: G->V)
        {
            run_Dijkstra(G, vertex_u->index, &w_);
            for (auto vertex_v: G->V)
            {
                D[vertex_u->index][vertex_v->index] = vertex_v->d + h[vertex_v->index] - h[vertex_u->index];
                if (vertex_v->pi != nullptr)
                {
                    PI[vertex_u->index][vertex_v->index] = vertex_v->pi->index;
                }
                else{
                    PI[vertex_u->index][vertex_v->index] = 2000000000;
                }
            }
        }
        return {D, PI};
    }
}


/**
 * @brief 输出Johnson算法的运行结果
 * 
 * @param D_PI Johnson算法运行后得到的D矩阵和PI矩阵
 */
void Johnson::output_Johnson_result(vector<vector<vector<int>>>* D_PI){
    auto n_V = (*D_PI)[0].size();
    for (size_t s = 0; s < n_V; s++)
    {
        for (size_t i = 0; i < n_V; i++)
        {
            if (i != s && (*D_PI)[0][s][i] < 1000000000)
            {
                cout << (*D_PI)[0][s][i] << '\t';
            }
            else if (i == s)
            {
                cout << '0' << '\t';
            }
            else{
                cout << 'X' << '\t';
            }
        }
        cout << endl;
    }
}